package heap;

import stack_queue.PriorityQueue;

import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

/**
 * @program: play-structure
 * @author: baichen
 * 力扣347：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * 如：
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 参考前面统计频率的类
 **/
public class TopKFrequent {
    private class Freq implements Comparable<Freq> {
        int e, freq;     //元素e和频次freq

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        public int compareTo(Freq another) {
            //比较频次大小
            if (this.freq < another.freq)
                return 1;
            else if (this.freq > another.freq)
                return -1;
            else        //频次相等
                return 0;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        //统计频次，key是值，value是频次
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for (int num:nums){
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else
                map.put(num,1);
        }
        //利用优先队列求出前K个元素,这里是最大堆
        PriorityQueue<Freq> pq=new PriorityQueue<Freq>();
        for (int key:map.keySet()){
            if (pq.getSize()<k){    //队列元素大小小于指定的频次k
                pq.enqueue(new Freq(key,map.get(key))); //放入队列，此时Freq对象既有e又有freq
            }else if (map.get(key)>pq.getFront().freq){ //取出堆顶元素对应的频次值
                pq.dequeue();
                pq.enqueue(new Freq(key,map.get(key)));
            }
        }
        //将前K个元素放入LinkedList
        LinkedList<Integer> result=new LinkedList<>();
        while (!pq.isEmpty()){
            result.add(pq.dequeue().e);
        }
        return result;
    }
}
